class Node {
    constructor(isWord = false) {
        this.isWord = isWord
        this.next = new Map()
    }
}

export class Trie {
    constructor() {
        this.root = new Node()
        this.size = 0
    }

    getSize() {
        return this.size
    }

    isEmpty() {
        return this.size === 0
    }

    add(word) {
        let cur = this.root

        for (let i = 0; i < word.length; i++) {
            const c = word[i]

            if (cur.next.has(c) === false) {
                cur.next.set(c, new Node())
            }
            cur = cur.next.get(c)
        }

        if (cur.isWord === false) {
            cur.isWord = true
            this.size++
        }

    }

    contains(word) {
        let cur = this.root

        for (let i = 0; i < word.length; i++) {
            const c = word[i]

            if (cur.next.has(c) === false) {
                return false
            }
            cur = cur.next.get(c)
        }

        return cur.isWord
    }

    isPrefix(prefix) {
        let cur = this.root

        for (let i = 0; i < prefix.length; i++) {
            const c = prefix[i]

            if (cur.next.has(c) === false) {
                return false
            }
            cur = cur.next.get(c)
        }

        return true
    }

}